653. 两数之和 IV - 输入二叉搜索树

Similar Question

leading to the advanced question

Solution Tips

方案一: 哈希表

var findTarget = function(root, k) {
    const set = new Set();
    const helper = (root, k) => {
        if (!root) {
            return false;
        }
        if (set.has(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return helper(root.left, k) || helper(root.right, k);
    }
    return helper(root, k);
};

方案二: 对撞指针

注意到二叉搜索树的中序遍历是升序排列的，我们可以将该二叉搜索树的中序遍历的结果记录下来，得到一个升序数组。